package 链表;

import java.util.List;

public class No206反转链表 {

    /**
     * 反转一个单链表。
     *
     * 示例:
     *
     * 输入: 1->2->3->4->5->NULL
     * 输出: 5->4->3->2->1->NULL
     */

    public static ListNode reverseList(ListNode head) {
        ListNode cur=head;
        ListNode last=null;//末尾肯定是null
        ListNode next;

        while (cur!=null){

            //保存下节点
            next=cur.next;

            //修改本节点
            cur.next=last;

            //保存本节点
            last=cur;

            //跑到下一个节点
            cur=next;
        }

        return last;
    }

    //自己写的递归写法
    public static ListNode reverseListDG(ListNode head) {

        if(head==null||head.next==null)
            return head;//如果是尾节点了,那么就返回自己

        //得到已经所有已经指向好的
        ListNode listNode = reverseListDG(head.next);//找到最终的那个节点,然后返回
        System.out.println("方法中:"+listNode.val);
        //返回的途中做一系列的操作
        head.next.next=head;//下一个节点(head.next)的指针(next)指向自己
        //本节点的指针置为null,这里置为了空会被弹出的节点重新执行上一句,将自己的指针指向上一节点
        /**
         * 这一句最终的性质是将原头节点的next指向为null,防止链表死循环
         */
        head.next=null;
        return listNode;//只会返回最终的那个节点
    }

    /**
     * 上方自己写的和下方官方解题一样
     */
    public ListNode reverseListGood(ListNode head) {
        ListNode prev = null;///上一个节点
        ListNode curr = head;//本节点
        ListNode nextTemp;//保存下一个节点
        while (curr != null) {
            //保存下一个节点
            nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    public static ListNode op(ListNode head){
        //1->2->3
        //1<-2<-3
        ListNode listNode=new ListNode();
        listNode.next=head;
        ListNode op=null;//上一个节点
        ListNode next;//下一个节点
        ListNode cur=listNode.next;

        while (cur!=null){

            next=cur.next;

            cur.next=op;

            op=cur;

            cur=next;
        }

        return op;
    }


    public static void main(String[] args) {
        ListNode listNode5=new ListNode(5,null);
        ListNode listNode4=new ListNode(4,listNode5);
        ListNode listNode3=new ListNode(3,listNode4);
        ListNode listNode2=new ListNode(2,listNode3);
        ListNode listNode1=new ListNode(1,listNode2);

        ListNode ok=listNode1;
        while (ok!=null){
            System.out.println(ok.val);
            ok=ok.next;
        }

        System.out.println("---");

        ListNode listNode = op(listNode1);

        ListNode cur=listNode;
        while (cur!=null){
            System.out.println(cur.val);
            cur=cur.next;
        }
    }

}
